Video conferencing, transmitting, and recording technologies commonly rely on video codecs for compressing and decompressing video signals. A conventional video codec includes both an encoder and a decoder. The encoder compresses video signals, and the decoder decompresses video signals. Codecs typically perform compression and decompression on “blocks” of video “frames,” where each block is a square array of pixels, such as 8×8 pixels, 16×16 pixels, and so on, for example, and each frame corresponds to a still snapshot of a video signal. A “pixel” is the smallest addressable unit of a video frame and provides a sample (e.g., a collection of red, green, and blue values) of the video signal at the addressed location. As used herein, the term “blocks” refers to both on-grid blocks, i.e., block-sized arrays of pixels positioned on a regular block grid of a frame, and off-grid blocks, i.e., block-sized arrays of pixels positioned off of the regular grid. Well-known video codecs include those conforming to H.264 or H.265 standards.
Video codecs typically use predictions to achieve efficient compression. To encode a current block of raw pixels, for example, an encoder may search for a block-sized array of previously-processed pixels that matches, or comes close to matching, the current block. To this end, the encoder performs many block-matching operations. Each block-matching operation compares the current block with a block-sized array of previously-processed pixels. Block matching may be exact or approximate. For exact block matching, the encoder compares the current block, pixel-for-pixel, with previously-acquired arrays of raw pixels, and identifies a matching block as the block-sized array of raw pixels that exactly matches the current block. For approximate block matching, the encoder compares the current block with arrays of reconstructed pixels, i.e., produced by a local decoder that receives encoded blocks, and identifies a matching block as the array of reconstructed pixels that best fits the current block. In both cases, the encoder generates displacement vectors and/or motion vectors (e.g., for intra-frame and inter-frame prediction, respectively) that identify the spatial and/or temporal position of the matching block relative to the current block.
The encoder then identifies a prediction block. Prediction blocks are based on reconstructed pixels rather than on raw pixels, so that a remote decoder, which cannot access raw pixels, is able to generate the same prediction blocks as the encoder. In the case of exact block matching, the prediction block is the block-sized array of reconstructed pixels that the local decoder has generated from an encoded version of the matching block. In the case of approximate block matching, the prediction block is simply the matching block. The encoder then subtracts the prediction block, pixel-for-pixel, from the current block to yield a residual block, which thus represents an error in the prediction. Typically, the encoder then transforms, quantizes, and entropy encodes the residual block to produce an encoded block. The encoder may then store the encoded block or send it to a remote decoder, along with information about the prediction (e.g., a prediction mode and a displacement vector and/or motion vector), which enables the decoder to reverse the encoding process and reconstruct a rendition of the current block.
One prior technique for performing exact block matching using a hash table. The hash table associates hash values of blocks with corresponding block locations in video frames. To find a block that matches a current block, an encoder hashes the current block and looks up the resulting value in the hash table. The encoder iterates through the block locations listed in the hash table for the computed value and attempts to identify a best candidate for a matching block.